package com.liang.bishi.wy;

import java.util.*;

/**
 * 第三题：动态规划计算最长公共子序列
 * 小易需要在河的两岸找到型号相同的桥墩，以搭建不相交的桥。
 * 输入两行表示两岸桥墩型号，桥墩数量不超过500，型号为正整数（≤2000），求小易最多能搭建多少座桥
 * 1 2 3
 * 1 2 4 3
 * <p>
 * 3
 */
public class Problem3 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取左岸桥墩型号
        String[] left = in.nextLine().split(" ");
        // 读取右岸桥墩型号
        String[] right = in.nextLine().split(" ");
        System.out.println(getMaxBridge(left, right));
    }

    private static int getMaxBridge(String[] left, String[] right) {
        int n = left.length;
        int m = right.length;
        // dp[i][j] 表示在左岸前 i 个桥墩和右岸前 j 个桥墩的范围内，可以搭建的最多桥梁数量
        int[][] dp = new int[n + 1][m + 1];
        // 遍历
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果桥墩型号相同，可以搭桥
                if (left[i - 1].equals(right[j - 1])) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 不同，取前一个状态的最大值：无法进行搭桥的情况
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        // 最大可搭建的桥梁数量
        return dp[n][m];
    }
}
